package medium;

/**
 * 不用乘除 取模计算两个数的商
 * 
 * @author ctk
 *
 */
public class DivideTwoIntegers {
	public static void main(String[] args) {
		DivideTwoIntegers d = new DivideTwoIntegers();
		System.out.println(d.divide2(-2147483648, 2));
	}

	// 超时
	public long divide1(long dividend, long divisor) {
		long result = 0;
		if (divisor != 0) {
			long temp = 0;
			if (dividend > 0 && divisor > 0) {
				while (temp < dividend) {
					if ((temp + divisor) > dividend)
						break;
					result++;
					temp = temp + divisor;
				}
			} else if (dividend < 0 && divisor > 0) {
				while (temp > dividend) {
					if ((temp - divisor) < dividend)
						break;
					result--;
					temp = temp - divisor;
				}
			} else if (dividend > 0 && divisor < 0) {
				while (temp < dividend) {
					if ((temp - divisor) > dividend)
						break;
					result--;
					temp = temp - divisor;
				}

			} else if (dividend < 0 && divisor < 0) {
				while (temp > dividend) {
					if ((temp + divisor) < dividend)
						break;
					result++;
					temp = temp + divisor;
				}
			} else if (dividend == 0)
				result = 0;
		} else {
			result = Integer.MAX_VALUE;
		}
		return result;
	}

	public int divide2(int dividend, int divisor) {
		if (divisor == 0) {
			return dividend >= 0 ? Integer.MAX_VALUE : Integer.MIN_VALUE;
		}

		if (dividend == 0) {
			return 0;
		}

		if (dividend == Integer.MIN_VALUE && divisor == -1) {
			return Integer.MAX_VALUE;
		}

		boolean isNegative = (dividend < 0 && divisor > 0) || (dividend > 0 && divisor < 0);

		long a = Math.abs((long) dividend);
		long b = Math.abs((long) divisor);
		int result = 0;
		while (a >= b) {
			int shift = 0;
			while (a >= (b << shift)) {
				shift++;
			}
			a -= b << (shift - 1);
			result += 1 << (shift - 1);
		}
		return isNegative ? -result : result;
	}
}
